home *** CD-ROM | disk | FTP | other *** search
/ The World's Largest Collection of Windows Software / The World's Largest Collection of Windows Software - Disc 1.iso / connect / _j2 / wvnsc926 / shellsor.c < prev    next >
C/C++ Source or Header  |  1994-09-21  |  4KB  |  114 lines
  1.  
  2. /*
  3.  *
  4.  * $Id: shellsor.c 1.8 1994/09/03 01:08:03 rushing Exp $
  5.  * $Log: shellsor.c $
  6.  * Revision 1.8  1994/09/03  01:08:03  rushing
  7.  * define huge away for win32
  8.  *
  9.  * Revision 1.7  1994/09/02  23:50:14  rushing
  10.  * shellsort is now huge
  11.  *
  12.  * Revision 1.6  1993/12/08  01:28:38  rushing
  13.  * new version box and cr lf consistency
  14.  *
  15.  * Revision 1.5  1993/07/08  19:41:06  rushing
  16.  * fixed unsigned bug again.  strange.
  17.  *
  18.  * Revision 1.4  1993/07/06  21:09:09  cnolan
  19.  * win32 support
  20.  *
  21.  * Revision 1.2  1993/06/28  17:53:24  rushing
  22.  * fixed compiler warnings
  23.  *
  24.  * Revision 1.1  1993/02/16  20:53:50  rushing
  25.  * Initial revision
  26.  *
  27.  *
  28.  */
  29.  
  30. /* Shellsort is a variation on Insertion Sort that is virtually unbeatable
  31.  * on small data sets.  Insertion Sort is slow because it only exchanges
  32.  * adjacent elements.  Shellsort circumvents this by allowing the exchange
  33.  * of elements that are farther apart.  It works by first performing Insertion
  34.  * Sort on subsets of the data.  For example, Shellsort might first sort
  35.  * the set of elements 1, 6, 11, 16... relative to each other--the effect
  36.  * is that the elements in that subset are moved much closer to their final
  37.  * positions.  At first the sets are wide-spread, perhaps every fortieth
  38.  * element.  Then it repeats using a tighter set, perhaps every fourteenth
  39.  * element, then every fourth element.  Each of these passes is much cheaper
  40.  * than a traditional Insertion Sort pass.  The effect of the passes is that
  41.  * the data set is mutated to be in "almost sorted" order.  The final insertion
  42.  * sort pass can then go very quickly because insertion sort does very well on
  43.  * almost sorted data.  In other words, at first the elements take large leaps
  44.  * to the general location they belong and successively smaller steps move the
  45.  * element to its precise place. I call this algorithm "inscrutable sort"
  46.  * because even after having coded the algorithm, I still have trouble
  47.  * following the animation.  No one has been able to analyze this algorithm
  48.  * rigorously; the functional form of the running time is conjectured to be
  49.  * O(N^1.25).  Shellsort may be a bit mysterious, but it is an good general
  50.  * purpose sort since it has excellent performance and the code you must write
  51.  * is only slightly more complex than Insertion Sort.
  52.  *
  53.  * Author: Julie Zelenski, NeXT Developer Support
  54.  * You may freely copy, distribute and reuse the code in this example.
  55.  * NeXT disclaims any warranty of any kind, expressed or implied, as to
  56.  * its fitness for any particular use.      qsort
  57.  */
  58.  
  59. #ifdef WIN32
  60. #include <windef.h>
  61. #endif
  62.  
  63. #include <stdio.h>
  64. #include <string.h>
  65.  
  66. #ifdef WIN32
  67.   #define __far far
  68.   #define huge far
  69.   #define       __near near
  70. #endif
  71.  
  72.  
  73. #define memSwap(a,b,unused) tmp = *(char huge * huge *)(a); \
  74.   *(char huge * huge *)(a) = *(char huge * huge *)(b); *(char huge * huge *)(b) = tmp;
  75.  
  76. void
  77. ShellSort (void huge * huge * base,
  78.        size_t nElements,
  79.        size_t width,
  80.        int (*compare) (void const huge *elem1, void const huge * elem2))
  81. {
  82. #define STRIDE_FACTOR 3
  83.   unsigned int c, stride;
  84.   int d;
  85.   char far *tmp;
  86.   int found;
  87.  
  88.   stride = 1;
  89.   while (stride <= nElements)
  90.     stride = stride * STRIDE_FACTOR + 1;
  91.  
  92.   while (stride > (STRIDE_FACTOR - 1))
  93.     {
  94.       stride = stride / STRIDE_FACTOR;
  95.       for (c = stride; c < nElements; c++)
  96.     {
  97.       found = 0;
  98.       d = c - stride;
  99.       while ((d >= 0) && !found)
  100.         {
  101.           if (compare ((char huge *) base + (d + stride) * width, (char huge *) base + d * width) < 0)
  102.         {
  103.           memSwap ((char huge *) base + (d + stride) * width, (char huge *) base + d * width, width);
  104.           d -= stride;
  105.         }
  106.           else
  107.         {
  108.           found = 1;
  109.         }
  110.         }
  111.     }
  112.     }
  113. }
  114.